Ch.2 Proof Techniques

Rules of Inference

From textbook, page 66

Rule	Tautology	Name
$\begin{array}{l}p\\p\implies q\\\hline\therefore q\end{array}$	$[p\land(p\implies q)]\implies q$	Modus ponens
$\begin{array}{l}\lnot q\\p\implies q\\\hline\therefore\lnot q\end{array}$	$[\lnot q\land(p\implies q)]\implies\lnot p$	Modus tollens
$\begin{array}{l}p\implies q\\q\implies r\\\hline\therefore r\end{array}$	$[(p\implies q)\land(q\implies r)]\implies (p\implies r)$	Hypothetical syllogism
$\begin{array}{l}p\lor q\\\lnot p\\\hline\therefore q\end{array}$	$[(p\lor q)\land\lnot p]\implies q$	Dysjunctive syllogism
$\begin{array}{l}p\\\hline\therefore p\lor q\end{array}$	$p\implies(p\lor q)$	Addition
$\begin{array}{l}p\land q\\\hline\therefore p\end{array}$	$(p\land q)\implies p$	Simplification
$\begin{array}{l}p\\q\\\hline\therefore p\land q\end{array}$	$(p)\land(q)\implies(p\land q)$	Conjunction
$\begin{array}{l}p\lor q\\\lnot p\lor r\\\hline\therefore q\lor r\end{array}$	$(p\lor q)\land(\lnot p\lor q)\implies(q\lor r)$	Resolution

Example 2.1

"It is not sunny this afternoon and it is colder than yesterday."
"We will go swimming only if it is sunny."
"If we do not go swimming, than we will take a canoe trip."
"If we take a canoe trip, then we will be home by sunset."
$\therefore$ "We will be home by sunset."

We set
$p=$ "It is sunny this afternoon."
$q=$ "It is colder than yesterday"
$r=$ "We will go swimming"
$s=$ "We will take a canoe trip"
$t=$ "We will be home by sunset"
Note: "Only if" is one-directional
$\begin{array}{lr}1:&\lnot p\land q\\2:&r\implies p\\3:&\lnot r\implies s\\4:&s\implies t\\\hline&t\end{array}$
$\begin{array}{rrl}5:&\lnot p&\text{from 1 and simplification}\\6:&\lnot r&\text{from 2 and 5 and Modus tollens}\\7:&s&\text{from 3 and 6 and Modus ponens}\\8:&t&\text{from 4 and 7 and Modus ponens}\end{array}$

Direct proof: Check if proposition $q$ is True by starting with proposition $q$ that we know is true, and use conditional statements to reach $q$
$p_1\implies p_2\implies\cdots\implies q$
Example 2.2: Direct Proof
Natural number $N$ is even if there is a natural number $k$ s.t. $N=2k$
Proposition: If $N$ and $M$ are even then $N-M$ is also even
Proof: Because $N$ and $M$ are even, $\exists k,l$ s.t. $N=2k$ and $M=2l$ . Then, $N-M=2k-2l=2(k-l)$ . $\blacksquare$
This is technically an incorrect proof because the definition of even only coners natural numbers, so if $k-l<0$ , the logic doesn't hold. Therefore, it is important to establish proper definitions (in this case that $k$ can be any integer, positive or negative)
Counterexamples: Check if proposition $q$ is False by finding a single false example (something can't be true for all $x$ if its for any any one $x$ )
- similar, proof by example: e.g. Show that there exists an even number that is not divisible by $4$
contrapositive: Using the fact that $(p\implies q)\equiv(\lnot q\implies\lnot p)$ , we prove $\lnot q\implies \lnot p$ to indirectly prove that $p\implies q$
Example 2.3: Proof by Contrapositive
Show that if $n^2$ is odd, then $n$ is odd.
We prove by proving the contrapositive, i.e. if $n$ is even, $n^2$ is even.
Let $n=2k$ for some integer $k$ . Then $n^2=(2k)^2=2(2k^2)$ . Since $2k^2$ is an integer, $n^2$ is even. $\blacksquare$
Direct Proof variant
Let $n^2=2k+1$ for some integer $k$ . Then $n^2-1=2k\implies (n-1)(n+1)=2k$ thus $n-1$ or $n+1$ must be even, but since their difference is $2$ , both must be even. Thus, $n$ must be an odd integer. $\blacksquare$
proof by cases
- To prove something for all $x$ ( $\forall x$ ), split the domain of $x$ into subsets $C_1,...,C_k$ and check $P(x)$ is true $\forall x$ in each $C_i$
Example 2.4: Proof by Cases
Show that if $x<-1$ or $x>1$ , then $|x|>1$ .
Case 1: $x>1$
This is obvious.
Case 2: $x<-1$
Then $x$ is negative, so the absolute value $|x|=-x$ . So $|x|>-(-1)=1$ .
Thus, in all possible cases, $|x|>1$ . $\blacksquare$
Proof by construction
- show something exists by explaining how it could be made- but without necessarily constructing it explicitly
Example 2.5: Proof by Construction
Show that there exists irrational numbers $x,y$ such that $x^y$ is rational
$\sqrt{2}$ is irrational. Consider $\sqrt{2}^{\sqrt{2}}$ . If this is rational, we take $x=y=\sqrt{2}$ and we are done. Otherwise, take $\left(\sqrt{2}^{\sqrt{2}}\right)^{\sqrt{2}}=\sqrt{2}^2=2$ , and we are stilll done. $\blacksquare$
Proof by contradiction: prove something by showing that the opposite leads to a contradiction (see below)

Proof by Contradiction

Show that if " $n^2$ is odd" $(p)$ , then " $n$ is odd" $(q)$
To show $p\implies q$ , can show $\lnot q\implies\lnot p$ (contrapositive), but under Proof by Contradiction:
Assume $n$ is even [ $\lnot$ ( $n$ is odd)]. Then by the definition of even numbers, $n=2k$ for some $k\in\mathbb{Z}$ . Thus, $n^2=(2k)^2=2(2k^2)$ is also even, which contradicts our statement. Hence, our assumption is false and $n$ is odd.

Example 2.6: Infinite Primes

Show that there are infinitely many prime numbers.
Proof by contradiction:
Assume there are finitely many primes, $p_1,p_2,...,p_N$ . (If we can find just one more, we contradict the statement) Consider $K=p_1p_2\cdots p_N+1$ . This is a natural number. If $K$ is prime, then $K>p_i$ for $1\le i\le N$ , so we have a new prime number, contradicting the statement that there are only $N$ primes. If $K$ is not prime, then there is a prime $q$ that divides $K$ . However, $q\ne p_i$ for all $1\le i\le N$ (can be proven by contradiction). Thus, we have a new prime number.
In both cases, we found a new prime number. Hence, our assumption that there are finitely many prime numbers is false, proving our theorem.

Example 2.7: Irrationality of

\sqrt2

Prove $\sqrt{2}$ is irrational.
Suppose $\sqrt{2}$ is rational. Then it can be expressed as a fraction $\frac{m}{n}$ where $m,n\in\mathbb{Z}$ , $n\ne0$ and $\text{gcd}(m,n)=1$ . Squaring both sides and clearing the denominator gives $2n^2=m^2$ . Since $m^2$ is even, $m$ must also be even, so $m=2k$ for some integer $k$ . Thus, $2n^2=(2k)^2\implies n^2=2k^2$ . Since $n^2$ is even, $n$ must also be even, so $n=2l$ for some $l$ . However, this makes $\text{gcd}(m,n)=2$ , a contradiction. Therefore, $\sqrt{2}$ must be irrational.

Proof Tip

Finding an invariant quantity.

Example 2.8

Suppose you are moving on the plane according to the following rule:

From point $(x,y)$ , you go to $(0.6x+0.8y,0.8x-0.6y)$

If you start at the origin, can you reach $(1,1)$ $(1, 1)$ ?
- No, because $(0,0)$ maps to itself.
Can you reach $(1,1)$ $(1, 1)$ from $(0.5,0.5)$ $(0.5, 0.5)$ ?
- $(0.6x+0.8y)^2+(0.8x-0.6y)^2=x^2+y^2$ , so no matter how many times you move, the quantity $x^2+y^2$ is invariant.
- At $(1,1)$ , this quantity is $1^2+1^2=1$ . At $(0.5,0.5)$ , this quantity is $0.5^2+0.5^2=0.5$ , which are different, so no.